package com.leetcode.LC_MED;

import java.util.List;

public class LC120_2 {
    public int minimumTotal(List<List<Integer>> triangle) {

        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int a = triangle.size();
        int b = triangle.get(a - 1).size();
        int[][] ints = new int[a][b];
        int tmp = 0;
        for (List<Integer> list : triangle) {
            for (int i = 0; i < list.size(); i++) {
                ints[tmp][i] = list.get(i);
            }
            tmp++;
        }
        int[][] f = new int[a][b];
        f[0][0] = ints[0][0];
        for (int i = 1; i < ints.length; i++) {
            for (int j = 0; j <= i; j++) {
                f[i][j] = Integer.MAX_VALUE;
                if (j > 0)
                    f[i][j] = Math.min(f[i - 1][j - 1] + ints[i][j], f[i][j]);
                if (i > j)
                    f[i][j] = Math.min(f[i - 1][j] + ints[i][j], f[i][j]);
                System.out.print(f[i][j] + " ");
            }
            System.out.println();
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < b; i++) {
            min = Math.min(min, f[a - 1][i]);
        }

        return min;
    }

    public int minimumTotal2(List<List<Integer>> triangle) {

        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int a = triangle.size();
        int b = triangle.get(a - 1).size();
        int[][] ints = new int[a][b];
        int tmp = 0;
        for (List<Integer> list : triangle) {
            for (int i = 0; i < list.size(); i++) {
                ints[tmp][i] = list.get(i);
            }
            tmp++;
        }
        int[][] f = new int[2][b];
        f[0][0] = ints[0][0];
        for (int i = 1; i < ints.length; i++) {
            for (int j = 0; j <= i; j++) {
                f[i & 1][j] = Integer.MAX_VALUE;
                if (j > 0)
                    f[i & 1][j] = Math.min(f[i - 1 & 1][j - 1] + ints[i][j], f[i & 1][j]);
                if (i > j)
                    f[i & 1][j] = Math.min(f[i - 1 & 1][j] + ints[i][j], f[i & 1][j]);
                System.out.print(f[i & 1][j] + " ");
            }
            System.out.println();
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < b; i++) {
            min = Math.min(min, f[a - 1 & 1][i]);
        }

        return min;
    }
}
